1. Field of the Invention
The present invention relates to storage systems. More particularly, the present invention relates to a system and a method for managing a storage system.
2. Description of the Related Art
Policy-based management has been advocated as a panacea that will allow storage administrators to manage larger amounts of storage than are currently managed. For a policy-based management approach, system administrators specify high level policies (goals) with respect to performance, reliability, security, backup, restore, etc., and the storage management software uses a rule engine to automatically convert the high-level policies into low-level storage actions. As implemented, the responsibility of storage management has accordingly been transferred from system administrators to storage-management software providers. Storage management software providers must deal with complexity associated due to the presence of a large number of heterogeneous devices, business rules, users and storage management actions. Software providers also must ensure that their management software is general enough to handle changing workloads and system configurations, that is, not “brittle.”
In complex storage environments, when a particular high-level goal is not being satisfied, there are potentially multiple storage management actions that can be taken for rectifying the problem. For a given system state, there can potentially be multiple rules that are applicable. Currently, rule-based systems handle such situations in an ad-hoc fashion by randomly selecting one of the available rules. It is not easy for the reasoning engine to a priori prioritize which particular storage management action to choose because each storage management action has complex side-affects that could potentially take the system into, for example, a thrashing mode or into sub-optimal states. Further, each respective action has a different cost associated with its invocation that must also be taken into account. A close analogy to this situation would be a chess match in which potential consequences of a particular move are not clear until many moves later. Consequently, chess players try to mentally analyze many moves ahead without actually making any moves.
N-step look-ahead algorithms are in use in Artificial Intelligence (AI) game theory domains, such as chess and checkers. N-step look-ahead algorithms are also in use in disk I/O scheduling and CPU instruction scheduling domains. Similarly, monitoring of real systems to create what-if analysis is currently being used in the database domain. Research relating to N-step look-ahead algorithms can be divided into three categories: (1) application domains of N-step lookahead; (2) monitoring information to create system models; and (3) N-step lookahead in Artificial Intelligence (AI) and planning.
In the category of application domains research, N-step lookahead implementations have domain-specific semantics for modeling and reasoning the actions within a system. For instance, traditional buffer management algorithms that minimize the number of I/O disk accesses for optimizing prefetching and caching in parallel I/O systems are substantially suboptimal in a parallel I/O system in which multiple I/Os proceed simultaneously. See, for example, M. Kallahalla et al., “Optimal prefetching and caching for parallel I/O systems,” In ACM Symposium on Parallel Architectures and Algorithms, pp. 219-228, 2001, which discloses an online algorithm with a global L-block lookahead that gives the buffer management algorithm a lookahead consisting of L distinct requests.
In S. J. Beaty, “Lookahead scheduling,” ACM SIGMICRO Volume 23, Issue 1-2 (December 1992), a lookahead scheduling technique, the Data Dependence DAG (DDD), is disclosed for executing instructions. Additionally, according to Beaty, lookahead combined with other scheduling techniques can increase the likelihood of generating correct schedules.
Simulation in distributed systems is dependent on detection of model-inherent concurrency, which is related to the prediction of the future behavior of each logical simulation process. See, for example, J. W. Janneck, “Generalizing lookahead-behavior prediction in distributed simulation,” In Proceedings of the twelfth workshop on Parallel and distributed simulation, pp. 12-19, 1998, which discloses a generalization of traditional approaches for behavior prediction using a lookahead algorithm.
For lookahead scheduling in disks, see, for example, T. Yeh et al., “Competitive analysis of on-line disk scheduling,” Theory of Computing Systems, Vol. 31, pp. 491-506, 1998, which analyzes the problem of an on-line disk scheduling in which a look ahead at the next k variables that are to be read can be performed and from that knowledge, the order in which to read the variables from the disk can be selected for minimizing the seek start-up time.
In the category of monitoring information to create system models; M. Selter et al., “Self-Monitoring and Self-Adapting Operating Systems,” In Proceedings of the Sixth Workshop on Hot Topics in Operating Systems, May 1997, discloses Vino, a self-monitoring and self-adapting operating system that performs continuous monitoring of operating system activity to construct a database of performance statistics. The data is classified appropriately and off-line analysis is performed for constructing a characterization of the system under normal behavior and for detecting anomalous behavior. The component adaptations are all predetermined, fixed implementations.
In the domain of databases, approaches such as SMART and AutoAdmin use query optimizers that can reason about the “what if” scenarios for automated index selection in databases. For the SMART implementation, see, for example, G. M. Lohman et al., “DB2 Advisor: An optimizer Smart Enough to Recommend Its Own Indexes,” Proceedings, 16th IEEE Conference on Data Engineering, San Diego, Calif., 2000. For AutoAdmin, see, for example, S. Chaudhuri et al., “AutoAdmin ‘What-if’ Index Analysis Utility,” Proceedings ACM SIGMOD Conference, Seattle 1998, pp. 367-378. The SMART system is continuously monitored and the performance of each query recorded. The optimizer uses past history to create the cost model for the operations in the query, which is then used to refine the execution plans.
In the category of AI and Planning theory, the concept of lookahead has been used extensively in game-theory, which is the science of strategy, and attempts to determine mathematically and logically the actions that “players” should take to secure the best outcomes for themselves in a wide array of“games.” The games studied range from chess to child rearing and from tennis to takeovers. But the games all share the common feature of interdependence. That is, the outcome for each participant depends upon the choices (strategies) of all. Deep Blue, for example, was built to examine 200 million possible moves per second and to look ahead as many as fourteen turns of play (considering all the permutations of the adversary moves). The lookahead algorithm is combined with search algorithms, such as A*, Simulated Annealing, Hill-climbing, and Forward pruning. See, for example, P. Norvig, Paradigms of AI Programming: Case Studies in Common Lisp, 1991, and H. -D. Bocker et al., “Interactive Problem Solving Using Log.”
Planning theory is generally referred to in the context of robotics, artificial intelligence, and control theory. Within robotics, the focus is on designing algorithms that generate useful motions by processing complicated geometric models. Within artificial intelligence, the focus is on designing systems that use decision-theoretic models compute appropriate actions. Within control theory, the focus of the presentation is on algorithms that numerically compute feasible trajectories or even optimal feedback control laws. There are multiple approaches for lookahead in each of these domains. Interesting techniques for mapping lookahead algorithms in game theory as search heuristics in planning algorithms are described in E. J, Sandewall, “A Planning Problem Solver Based on Look-Ahead in Stochastic Game Trees,” Journal of the ACM (JACM), Volume 16, Issue 3, July 1969.
Consequently, what is needed is a technique for managing a storage system that, in response to an alarm condition, selects an action that optimizes the stability of a storage system, a prerequisite of the storage system and a transient cost of invoking the selected action.